/**
 * 
 */
package uk.ac.manchester.cs.graph;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

/**
 * Same as Tree but with multiple roots
 * 
 * @author Pavel Klinov
 *
 * pklinov@cs.man.ac.uk, pklinov@clarkparsia.com
 * 
 * 4 Jul 2010
 */
public class Forest<T> {

	private List<Node<T>> m_roots = null;
	
    public Forest(T root) {
    	
    	init(Collections.singletonList(root));
    }    
 
    public List<Node<T>> getRoots() {
    	
        return m_roots;
    }
 

    public void setRoots(List<Node<T>> roots) {
    	
        m_roots = roots;
        
        for (Node<T> root : roots) root.setParent( null );
    }
     
    public List<Node<T>> nodeList(Node<T> start) {
    	
        List<Node<T>> list = new ArrayList<Node<T>>();
 
        walk(start, list, false);
        
        return list;
    }    
    
    public List<T> dataList(Node<T> start) {
    	
    	List<T> list = new ArrayList<T>();
    	
    	dataWalk(start, list, false);
    	
    	return list;
    }
    
    
    public List<Node<T>> getLeafs(Node<T> start) {
    	
        List<Node<T>> list = new ArrayList<Node<T>>();
        
        walk(start, list, true);
        
        return list;
    }
    
    public List<T> getLeafObjects(Node<T> start) {
    	
    	List<T> list = new ArrayList<T>();
    	
    	dataWalk(start, list, true);
    	
    	return list;
    }    
    
    public String toString() {

    	StringBuffer sb = new StringBuffer();
    	
    	for (Node<T> root : m_roots) root.output(sb, 0);
    	
    	return sb.toString();
    }
    
    /**
     * Walks the Forest in pre-order style. This is a recursive method, and is
     * called from the toList() method with the root element as the first
     * argument. It appends to the second argument, which is passed by reference
     * as it recurses down the tree.
     * @param element the starting element.
     * @param list the output of the walk.
     */
    private void walk(Node<T> element, List<Node<T>> list, boolean leafsOnly) {
    	
    	if ((!leafsOnly || element.isLeaf()) && !element.isDead()) {
    		
    		list.add(element);
    	}
        
        for (Node<T> data : element.getChildren()) {
        	
        	if (!data.isDead()) {
        		walk(data, list, leafsOnly);
        	}

        }
    }

    private void dataWalk(Node<T> element, List<T> list, boolean leafsOnly) {
    	
    	if ((!leafsOnly || element.isLeaf()) && !element.isDead()) {

    		list.add(element.getObject());
    	}
        
        for (Node<T> data : element.getChildren()) {

        	if (!data.isDead()) {
        		dataWalk(data, list, leafsOnly);
        	}
        }
    }
    
    
    public Forest<T> cloneForest() {
    	
    	Forest<T> forest = newForest();
    	
    	if (null != m_roots) {
    		
    		List<Node<T>> roots = new ArrayList<Node<T>>(m_roots.size());
    		
    		for (Node<T> root : m_roots) {
    			//clone will recursively clone nodes	
    			roots.add( root.cloneNode( null ) );
    		}
    		
    		forest.setRoots( roots );
    	}
    	
    	return forest;
    }
    
    protected Forest<T> newForest() {
    	
    	return new Forest<T>(null);
    }
    
	protected void init(Collection<T> objects) {
		
		m_roots = new ArrayList<Node<T>>(objects.size());
		
		for (T object : objects) m_roots.add( new Node<T>(null, object) );
	}	
}
